The present invention relates generally to filtering and more particularly relates to a method for performing frequency domain filtering employing a real to analytic transform.
Many digital signal processing (DSP) applications employ digital filtering techniques in order to filter out unwanted signals or noisy frequency components within signals. The implementation of such digital filters is often performed via the use of finite impulse response (FIR) filtering which is a well known method of implementing a convolution. This method requires K multiply and accumulate (MAC) operations per input, where K is the number of taps implemented in the filter. The method generates an inherent delay of approximately K/2 samples. If the sampling frequency of the input (and output) signals is FS then the number of MACs performed every second is FS*K. For large filters or at high sampling rates this may become a burden for the computational machine performing the processing.
A technique well known in the art that can be used to overcome these tight computational constraints employs Fast Convolution (FC) which utilizes the Fast Fourrier Transform (FFT) and the Inverse Fast Fourrier Transform (IFFT). While this technique may dramatically reduce the computational requirements for the processor, it requires gathering and processing the data in blocks of size N, with N usually being a radix-2 quantity. In order to gain a significant reduction of the computational requirements, N has to be significantly larger than K.
The major disadvantage of this method is that it introduces an inherent delay of size N, thus increasing the delay significantly with respect to the straightforward FIR method.
Numerous applications of Fast Convolution are known in the art. The technique is mostly used where the inherent delay introduced by the processing is either not critical to the application or is needed in order to compensate for other delays in the system.
An example of the use of the Fast Convolution technique may be found in voice band modem applications such as ITU V.32bis or ITU V.34. The technique is used to remove the echo signal generated by various line conditions and impairments. In particular, the far end echo canceler (FEEC) cancels the received echo which was generated on the remote side. The round trip delay (RTD) of the echo ranges from 30 ms to 2 seconds. In order to properly compensate for this delay and in order not to consume an enormous amount of processing resources, the FEEC must delay the input signal using a delay registry whose depth is approximately the round trip delay.
Since these modem applications require an inherent delay to compensate for the RTD introduced by the physical conditions, they can easily incorporate a Fast Convolution in order to alleviate the computational burden of the filter used to emulate the echo path.
Further, if the line condition impairments, e.g., frequency domain multiplexing up conversion and down conversion, introduce a frequency offset, the FEEC must xe2x80x98rotatexe2x80x99 the emulated echo by the same frequency offset. The frequency offset can be tracked using phase locked loop (PLL) circuitry. However, the quadrature component of the transmitted signal must either be stored beforehand or derived from the in-phase component. The former doubles the delays registry whereas the latter requires the use of an additional Hilbert filter which increases the computational intensity.
A typical prior art modem scheme will now be described. Typical prior art modem implementation schemes, such as the one illustrated in FIG. 1, comprise a data access arrangement (DAA) 42, transmitter 32, receiver 34, digital to analog converter (D/A) 38 and analog to digital converter (A/D) 40. In addition, the full duplex voice band modem also employs finite impulse response (FIR) adaptive filters. Such FIR filters include the far end echo canceler 41 FIR, the near end echo canceler 33 FIR and the equalizer FIR within the receiver 34. During operation, the communication system embodying the modem is usually required to cope with a vast majority of different communication channels each posing diverse channel and echo impairments.
As discussed above, the relatively long length of the various filters that is required to cope with the worst case impairments requires a large amount of processor resources. In order to reduce the burden of the filter processing on CPU usage, several well known DSP techniques can be utilized in implementing the above mentioned FIR filters, such as the xe2x80x98overlap and savexe2x80x99 and the xe2x80x98overlap and addxe2x80x99 employing the FFT and the IFFT.
The use of such techniques as the xe2x80x98overlap and savexe2x80x99 and the xe2x80x98overlap and addxe2x80x99 methods in dedicated DSP hardware implementations can save a great deal of processor resources since such DSP processors have optimized hardware designed to perform signal processing functions. Examples of signal processing functions that are typically optimized and implemented in hardware include bit reversal, modulo counting, multiply and add functions, barrel shifters, etc. These hardware signal processing functions make possible highly optimized, fast and efficient FFT and IFFT implementations.
Accordingly, the present invention has been developed to provide a method of frequency domain filtering that overcomes the limitations and disadvantages of the prior art.
The limitations of prior art frequency domain fast convolution techniques include requiring an additional amount of CPU resources in cases where a Hilbert filtering transform is required in order to obtain the quadrature component from the in-phase one and create an analytic signal, i.e., a complex signal which has an in-phase component as its real part and a quadrature component as its imaginary partxe2x80x94xe2x80x98real to analytic conversion.xe2x80x99 Such a signal has either positive or negative frequency components and therefore can easily undergo a frequency shift operation.
Accordingly, it is an object of the present invention to provide a method of implementing a real to analytic conversion utilizing frequency domain convolution which uses negligible additional CPU resources.
Another object of the present invention is to provide a method for real to analytic conversion utilizing an xe2x80x98overlap and savexe2x80x99 frequency domain convolution which uses negligible additional CPU resources.
There is provided in accordance with the present invention a method of performing real to analytic fast convolution on a real input block and a set of real Finite Impulse Response (FIR) coefficients to generate a complex output vector, the method comprising the steps of performing a first Fast Fourrier Transformation (FFT) on the real input block, performing a second FFT on the set of FIR coefficients, multiplying the results of the second FFT element by element with the frequency response of an ideal real to analytic transform to form a first product, multiplying the results of the first FFT element by element with the first product to yield a second product, performing an Inverse Fast Fourrier Transformation (IFFT) on the results of the second product to generate a complex output vector and forming a first real output block from the real portion of the output vector.
The ideal real to analytic transform may comprise a positive frequency real to analytic transform or a negative frequency real to analytic transform.
There is also provided in accordance with the present invention a method of performing real to analytic fast convolution on a real input block and a set of real Finite Impulse Response (FIR) coefficients to generate a complex output vector, the method comprising the steps of performing a first Fast Fourrier Transformation (FFT) on the real input block, performing a second FFT on the set of FIR coefficients, multiplying the results of the first FFT element by element with the frequency response of an ideal real to analytic transform to yield a first product, multiplying the results of the second FFT element by element with the first product to yield a second product, performing an Inverse Fast Fourrier Transformation (IFFT) on the second product to generate a complex output vector and forming a first real output block from the real portion of the output vector.
In addition, there is provided in accordance with the present invention an apparatus for performing filtering and frequency shifting on a real input signal, the apparatus outputting a real output signal, the apparatus comprising real to analytic means for performing a real to analytic fast convolution on the input signal, the real to analytic means operative to output a first complex signal, frequency generator means for generating a second complex signal represented by ejxcfx89t, the frequency generator means operative to generate the second complex signal having any arbitrary frequency xcfx89, a multiplier coupled to the real to analytic means and the frequency generator means, the multiplier for multiplying the first complex signal by the second complex signal to yield a third complex signal and real means coupled to the multiplier, the multiplier for taking the real component of the third complex signal to yield the real output signal.
The real to analytic means comprises means for performing a Fast Fourrier Transformation (FFT) on the real input to yield a first FFT output, means for performing a second FFT on a set of real Finite Impulse Response (FIR) coefficients to yield a second FFT output, means for multiplying the second FFT output element by element with the frequency response of an ideal real to analytic transform to yield a first product, means for multiplying the first FFT output element by element with the first product to yield a second product and means for performing an Inverse Fast Fourrier Transformation (IFFT) on the second product to generate the first complex signal.
Further, there is provided in accordance with the present invention a method of performing filtering and frequency shifting on a real input signal so as to generate a real output signal, the method comprising the steps of performing a real to analytic fast convolution on the input signal to yield a first complex signal, generating a second complex signal represented by ejxcfx89t, wherein the frequency generated is any arbitrary frequency xcfx89, multiplying the first complex signal by the second complex signal to yield a third complex signal and taking the real component of the third complex signal to yield the real output signal.
The step of performing a real to analytic fast convolution comprises the steps of performing a first Fast Fourrier Transformation (FFT) on the real input signal, performing a second FFT on a set of Finite Impulse Response (FIR) coefficients, multiplying the results of the second FFT element by element with the frequency response of an ideal real to analytic transform to form a first product, multiplying the results of the first FFT element by element with the first product to yield a second product and performing an Inverse Fast Fourrier Transformation (IFFT) on the results of the second product to generate a complex output vector.